/*
 * string search algorithms:
 * KMP, Sunday, Horspool, BM 
 * here implemented BM with Bad Character Rule, Good Suffix Rule.
 * Galil Rule is not implemented
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

#define SHIFT(shift, c) shift[(unsigned char)c]

void BuildBadCharacterShift(const char *pattern, int m, int *shift) {
  for (int i = 0; i < 256; ++i) shift[i] = m;
  for (int i = 0; i < m; ++i) {
    SHIFT(shift, pattern[i]) = m - i - 1;
  }
}

// assumes that input is valid
int SearchBadCharacterRule_(const char *text, int n, const char *pattern, int m,
                           const int *shift) {
  for (int j = 0; j <= n - m; ) {
    int i = m - 1;
    while (i >= 0 && pattern[i] == text[i + j]) --i;
    if (i < 0) return j;  
    j += std::max(SHIFT(shift, text[i + j]) - m + 1 + i, 1);    
  }
  return -1;
}

int SearchBadCharacterRule(const char *text, const char *pattern) {
  int n = strlen(text);
  int m = strlen(pattern);
  if (m > n || m == 0) return -1;
  int shift[256];
  BuildBadCharacterShift(pattern, m, shift);
  return SearchBadCharacterRule_(text, n, pattern, m, shift);
}

// suffix[i] is the max s that makes P[i-s+1, i] == P[m-s, m-1]
int *BuildSuffixes(const char *pattern, int m) {
  int *suffix = new int[m];
  suffix[m - 1] = m;
  for (int i = m - 2; i >= 0; --i) {
    int s = 0;
    // loop from i towords 0
    while (s <= i && pattern[i-s] == pattern[m-1-s]) ++s;
    suffix[i] = s;
  }
  return suffix;
}

int *BuildGoodSuffixShift(const char *pattern, int m) {
  int *shift = new int[m];
  // CASE 0: (default case) that no sub-string that matches to suffix,
  //          and also no prefix that matches to suffix.
  //          if there're, the value is rewrited
  for (int i = 0; i < m; ++i) shift[i] = m;

  int *suffix = BuildSuffixes(pattern, m);
  int j = 0;
  for (int i = m - 1; i >= 0; --i) {
    if (suffix[i] == i + 1) {
      // CASE 1: a prefix P[0, i] is found that matches suffix of pattern

      // for [j, m - 1 - suffix[i]], the shift is set to m-1-i, 
      // which is needed to align the last character with P[m-1]

      // NOTE: I think the if is not needed as there'll be no intersection
      // between [j, m - 1 - suffix[i]]s
      for (; j < m - 1 - i; ++j)
        if (shift[j] == m) shift[j] = m - 1 - i;
    }
  }

  // CASE 3: a sub-string is found that matches suffix,
  //         the shift is to align the last character of the sub-string
  //         with P[m-1]
  // Note: a prefix is a special case of this case, so part of its value
  //       is rewrited, however not changed
  for (int i = 0; i <= m - 2; i++) {
    shift[m - 1 - suffix[i]] = m - 1 - i;
  }

  delete[] suffix;
  return shift;
}

int SearchGoodSuffixRule_(const char *text, int n, const char *pattern, int m,
                         const int *shift) {
  for (int j = 0; j <= n - m; ) {
    int i = m - 1;
    while (i >= 0 && pattern[i] == text[i + j]) --i;
    if (i < 0) return j;  
    j += shift[i];    
  }
  return -1;
}

int SearchGoodSuffixRule(const char *text, const char *pattern) {
  int m = strlen(pattern);
  int n = strlen(text);
  if (m == 0 || m > n) return -1;
 
  int *shift = BuildGoodSuffixShift(pattern, m);

  int ret = SearchGoodSuffixRule_(text, n, pattern, m, shift);
  delete[] shift;
  return ret;
}

int BM_(const char *text, int n, const char *pattern, int m,
       const int *gs_shift, const int *bc_shift) {
  for (int j = 0; j <= n - m; ) {
    int i = m - 1;
    while (i >= 0 && pattern[i] == text[i + j]) --i;
    if (i < 0) return j;  
    j += std::max(gs_shift[i], SHIFT(bc_shift, text[i + j]) - m + 1 + i);
  }
  return -1;
}

int BM(const char *text, const char *pattern) {
  int m = strlen(pattern);
  int n = strlen(text);
  if (m == 0 || m > n) return -1;
 
  int *gs_shift = BuildGoodSuffixShift(pattern, m);

  int bc_shift[256]; 
  BuildBadCharacterShift(pattern, m, bc_shift);

  int ret = BM_(text, n, pattern, m, gs_shift, bc_shift);

  delete[] gs_shift;

  return ret;
}

template<typename Func>
void TestBM(Func search) {
  const char *text = "abccacedc";
  const char *pattern1 = "cedc";
  const char *pattern2 = "aced";
  int i1 = search(text, pattern1);
  int i2 = search(text, pattern2);
  if (i1 >= 0) printf("%s\n", text + i1);
  if (i2 >= 0) printf("%s\n", text + i2);
}

int main(int argc, const char *argv[]) {
  TestBM(SearchBadCharacterRule);
  TestBM(SearchGoodSuffixRule);
  TestBM(BM);
  return 0;
}

